package dp;

/**
 * leet-code(72) 编辑距离
 *
 * @author Ringo
 * @date 2021/10/1 22:23
 */
public class MinDistance {

    public static void main(String[] args) {
        String word1 = "horse", word2 = "ros";
        System.out.println(minDistance(word1, word2));
    }

    public static int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();

        // 有一个字符串为空串
        if (n * m == 0) {
            return m + n;
        }

        // dp[i][j] 表示 word1的前i位转换成word2的前j位, 需要的最少操作数
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                // abc -> fg: ab -> fg 只需删除'c'
                int left = dp[i - 1][j] + 1;
                // abc -> fg: abc -> f 只需增加'g'
                int down = dp[i][j - 1] + 1;
                // abc -> fg: ab -> f 将'c'替换为'g'
                int leftDown = dp[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    leftDown += 1;
                }
                dp[i][j] = Math.min(left, Math.min(down, leftDown));
            }
        }

        return dp[m][n];
    }

}
